package com.gxc.array;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 42. 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
public class Trap {

    public static void main(String[] args) {
        System.out.println(handle(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        System.out.println(handle(new int[]{4,2,0,3,2,5}));
    }

    /**
     * 双指针
     * 从两头移动，高度小的先移动，
     * @param height
     * @return
     */
    public static int handle(int[] height) {
        if (height.length < 2) return 0;
        int l = 0;
        int r = height.length - 1;
        int res = 0;
        int min = 0;
        int h = 0;
        while (l != r) {
            if (height[l] <= height[r]) {
                h = min - height[l];
                min = Math.max(height[l], min);
                l++;
            } else {
                h = min - height[r];
                min = Math.max(height[r], min);;
                r--;
            }
            res = res + (h>0?h:0);
        }
        return res;
    }

    /**
     * 动态规划
     * 对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下
     * 标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]
     *
     */
    class Solution {
        public int trap(int[] height) {
            int n = height.length;
            if (n == 0) {
                return 0;
            }

            int[] leftMax = new int[n];
            leftMax[0] = height[0];
            for (int i = 1; i < n; ++i) {
                leftMax[i] = Math.max(leftMax[i - 1], height[i]);
            }

            int[] rightMax = new int[n];
            rightMax[n - 1] = height[n - 1];
            for (int i = n - 2; i >= 0; --i) {
                rightMax[i] = Math.max(rightMax[i + 1], height[i]);
            }

            int ans = 0;
            for (int i = 0; i < n; ++i) {
                ans += Math.min(leftMax[i], rightMax[i]) - height[i];
            }
            return ans;
        }
    }

    /**
     * 单调栈
     * 维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减
     */
    class Solution2 {
        public int trap(int[] height) {
            int ans = 0;
            Deque<Integer> stack = new LinkedList<Integer>();
            int n = height.length;
            for (int i = 0; i < n; ++i) {
                while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                    int top = stack.pop();
                    if (stack.isEmpty()) {
                        break;
                    }
                    int left = stack.peek();
                    int currWidth = i - left - 1;
                    int currHeight = Math.min(height[left], height[i]) - height[top];
                    ans += currWidth * currHeight;
                }
                stack.push(i);
            }
            return ans;
        }
    }

    /**
     * 双指针
     * 注意到下标 i 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定
     * 当两个指针没有相遇时，进行如下操作：
     *
     * 使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；
     *
     * 如果 height[left]<height[right]，则必有 leftMax<rightMax，下
     * 标 left 处能接的雨水量等于 leftMax−height[left]，
     * 将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）；
     *
     * 如果 height[left]≥height[right]，则必有 leftMax≥rightMax，下
     * 标 right 处能接的雨水量等于 rightMax−height[right]，
     * 将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减 1（即向左移动一位）。
     *
     */
    class Solution3 {
        public int trap(int[] height) {
            int ans = 0;
            int left = 0, right = height.length - 1;
            int leftMax = 0, rightMax = 0;
            while (left < right) {
                leftMax = Math.max(leftMax, height[left]);
                rightMax = Math.max(rightMax, height[right]);
                if (height[left] < height[right]) {
                    ans += leftMax - height[left];
                    ++left;
                } else {
                    ans += rightMax - height[right];
                    --right;
                }
            }
            return ans;
        }
    }


}
